import java.util.*;

public class VPTree
{
	class VPNode extends NN
	{
		public String name;
		private Point p;
		private Double mu;
		private VPNode inner;
		private VPNode outer;
		private Double innerLowerBound;
		private Double innerUpperBound;
		private Double outerLowerBound;
		private Double outerUpperBound;
		private int pSample;
		private int dSample;

		public VPNode(Point DataBase[], int pSample, int dSample, String name)
		{
			super(DataBase);

			this.name = name;			

			p = null;
			if (DataBase.length <= 5) return;

			this.pSample = pSample;
			this.dSample = dSample;

			p = SelectVP(DataBase);
			//if (DataBase.length == 1) return;
			
			SortingElement distArray[] = CreateSortedIndex(p, DataBase);
/*
			System.out.println("========================");
			System.out.println(name);
			for (int i = 0; i < pointCount - 1; i++) System.out.println(DataBase[distArray[i].index].ID());
			System.out.println("========================");			
*/

			//System.out.println(DataBase.length);
			int len = distArray.length;
			mu = distArray[len / 2].value;

			ArrayList<Point> InnerData = new ArrayList<Point>();
			ArrayList<Point> OuterData = new ArrayList<Point>();
			for (int i = 0, idx = len / 2; i <  idx; i++)
				InnerData.add(DataBase[distArray[i].index]);
			if (len > 1)
			{
				for (int i = len / 2; i <  len; i++)
					OuterData.add(DataBase[distArray[i].index]);
			}

			inner = new VPNode(InnerData.toArray(new Point[InnerData.size()]), pSample, dSample, name + "_INNER");
			outer = new VPNode(OuterData.toArray(new Point[OuterData.size()]), pSample, dSample, name + "_OUTER");
			innerLowerBound = distArray[0].value;
			innerUpperBound = distArray[Math.max(len / 2 - 1, 0)].value;
			if (len > 1)
			{
				outerLowerBound = distArray[len / 2].value;
				outerUpperBound = distArray[len - 1].value;			
			}
		}

		public VPNode(Point DataBase[])
		{
			this(DataBase, 5, 10, "ROOT");
		}

		private Point SelectVP(Point DataBase[])
		{
			Random randomizer = new Random();
			int pointCount = DataBase.length;
			Double best_spread = 0.0;
			Point best = null;
			for (int i = 0; i < pSample; i++)
			{
				Point sample = DataBase[randomizer.nextInt(pointCount)];
				Point[] D = new Point[dSample];
				for (int j = 0; j < dSample; j++) D[j] = DataBase[randomizer.nextInt(pointCount)];
				SortingElement distArray[] = CreateSortedIndex(sample, D);
				int actualLength = 0;
				for (int j = 0; j < dSample; j++) if (distArray[j] != null) actualLength++;
				Double mu = distArray[actualLength/2].value;
				Double spread = 0.0;
				for (int j = 0; j < actualLength; j++) spread = spread + Math.pow(mu - distArray[j].value, 2);
//				System.out.println("||" + actualLength + "|| " + pointCount + "(" + spread + ") " + best_spread);
				if (spread >= best_spread)
				{
					best_spread = spread;
					best = sample;
				}
			}
			return best;
		}

		public SortingElement[] Query(Point q)
		{
			SortingElement[] retVal = new SortingElement[1];
			int index = Query(q, Double.MAX_VALUE, p).ID();
			retVal[0] = new SortingElement(index, DataBase[index].Distance(q));
			return retVal;
		}

		public Point Query(Point q, Double tau, Point best)
		{
			if ((p == null) || (pointCount <= 5)) 
			{
				for (int i = 0; i < pointCount; i++)
				{
					Double x = q.Distance(DataBase[i]);
//					System.out.println(DataBase[i].ID());
					if (x < tau)
					{
						tau = x;
						best = DataBase[i];
						System.out.println("best Now : " + best.ID() + ", score : " + best.Distance(q));
					}
				}
				return best;			
			}

			Double x = q.Distance(p);
			if (x < tau)
			{
				tau = x;
				best = p;
				System.out.println("best Now : " + best.ID() + ", score : " + best.Distance(q));
			}
			
			Double middle = innerUpperBound;
			if (pointCount > 2) middle = (middle + outerLowerBound) / 2;
			Point temp = best;
/*
			if (x < middle)
			{
//				System.out.println("LEFT");
				if ((x >= innerLowerBound) && (x <= innerUpperBound))
					temp = inner.Query(q, tau, best);
				if ((x >= outerLowerBound) && (x <= outerUpperBound))
					temp = outer.Query(q, tau, temp);
			}
			else
			{
//				System.out.println("RIGHT");
				if ((x >= outerLowerBound) && (x <= outerUpperBound))
					temp = outer.Query(q, tau, best);
				if ((x >= innerLowerBound) && (x <= innerUpperBound))
					temp = inner.Query(q, tau, temp);
			}
*/
			System.out.println(x + " : [" + innerLowerBound.toString() + ", " + innerUpperBound + "] [" + outerLowerBound + ", " + outerUpperBound + "]");
			if (x <= innerUpperBound)
			{
				System.out.println("INNER");
				temp = inner.Query(q, tau, best);
			}
			if (x >= outerLowerBound)
			{
				System.out.println("OUTER");
				temp = outer.Query(q, tau, temp);
			}
			return temp;
		}

		public Point getPoint() { return p;}
	}

	VPNode root;
	Point[] DataBase;

	public VPTree(Point DataBase[])
	{
		this.DataBase = DataBase;
		root = new VPNode(DataBase);
	}

	public NN.SortingElement[] Query(Point q)
	{
		return root.Query(q);
	}
}
